/*
 * Copyright (c) 1997, 1998, 2003, 2006 Aleksandar Samardzic
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the author may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include <assert.h>		/* for assert() function */
#include <stdlib.h>		/* for malloc() function */
#include <string.h>		/* for memset() function */
#include "tree.h"

/* Tree_Init - Tree class constructor */
void
Tree_Init(this)
     PTree          *this;
{
	this->pRoot = NULL;
}

/* Tree_Clean - Tree class destructor */
void
Tree_Clean(this)
     PTree          *this;
{
	PStack          stack;
	PTreeNode      *pNode,
	               *pChildNode;

	Stack_Init(&stack);
	Stack_Push(&stack, this->pRoot);

	/* deallocate storage for each node */
	for (; !Stack_IsEmpty(&stack);) {
		pNode = Stack_Pop(&stack);
		for (pChildNode = pNode->pFirstChild; pChildNode;
		     pChildNode = pChildNode->pNext)
			Stack_Push(&stack, pChildNode);
		free(pNode);
	}

	Stack_Clean(&stack);
}

/* Tree_AddItem - insert item into tree according to mode specified */
PTreeNode      *
Tree_AddItem(this, pItem, pNode, addMode)
     PTree          *this;
     void           *pItem;
     PTreeNode      *pNode;
     PAddMode        addMode;
{
	PTreeNode      *pNewNode;
	PTreeNode      *pSiblingNode;
	PTreeNode      *pChildNode;

	/* create new node */
	pNewNode = malloc(sizeof(PTreeNode));
	assert(pNewNode != NULL);
	memset(pNewNode, 0, sizeof(PTreeNode));
	pNewNode->pItem = pItem;

	if (pNode == NULL) {	/* tree was empty */
		this->pRoot = pNewNode;
		return pNewNode;
	}

	switch (addMode) {
	case CHILD:
		/* insert new node into list of pNode's children */
		if (pNode->numChildren == 0)
			pNode->pFirstChild = pNode->pLastChild = pNewNode;
		else
			pNode->pLastChild = pNode->pLastChild->pNext =
			    pNewNode;
		(pNode->numChildren)++;
		pNewNode->pParent = pNode;
		break;

	case SIBLING:
		/* create new sibling node and initialize it */
		pSiblingNode = malloc(sizeof(PTreeNode));
		assert(pSiblingNode != NULL);
		memcpy(pSiblingNode, pNode, sizeof(PTreeNode));

		/* fix siblings pointers */
		pNewNode->pParent = pNode;
		pSiblingNode->pParent = pNode;
		pSiblingNode->pNext = pNewNode;
		for (pChildNode = pSiblingNode->pFirstChild; pChildNode;
		     pChildNode = pChildNode->pNext)
			pChildNode->pParent = pSiblingNode;

		/* initialize parent node */
		pNode->pItem = NULL;
		pNode->numChildren = 2;
		pNode->pFirstChild = pSiblingNode;
		pNode->pLastChild = pNewNode;
		break;
	}
	return pNewNode;
}

/* TreePreorderIterrator_Attach - attach tree to iterator and initialize
 * iterator */
void
TreePreorderIterator_Attach(this, pTree)
     PTreePreorderIterator *this;
     PTree          *pTree;
{
	Stack_Init(&(this->stack));
	Stack_Push(&(this->stack), pTree->pRoot);
}

/* TreePreorderIterator_Next - return pointer to next item from tree */
int
TreePreorderIterator_Next(this, ppItem)
     PTreePreorderIterator *this;
     void          **ppItem;
{
	PTreeNode      *pCurr,
	               *pChildNode;

	if (Stack_IsEmpty(&(this->stack))) {	/* end of preorder
						 * iteration */
		Stack_Clean(&(this->stack));
		return 0;
	}

	/* get iteration current node */
	pCurr = Stack_Pop(&(this->stack));
	*ppItem = pCurr->pItem;

	/* remember children of current node for further iteration */
	for (pChildNode = pCurr->pFirstChild; pChildNode;
	     pChildNode = pChildNode->pNext)
		Stack_Push(&(this->stack), pChildNode);
	return 1;
}

/* TreeRightIterator_Attach - attach tree branch to iterator and
 * initialize iterator */
void
TreeRightIterator_Attach(this, pFirst)
     PTreeRightIterator *this;
     PTreeNode      *pFirst;
{
	this->pCurr = pFirst;
}

/* TreeRightIterator_Next - return pointer to next item from tree branch */
int
TreeRightIterator_Next(this, ppItem)
     PTreeRightIterator *this;
     void          **ppItem;
{
	if (!this->pCurr)	/* end of iteration */
		return 0;

	*ppItem = this->pCurr->pItem;
	this->pCurr = this->pCurr->pNext;
	return 1;
}

/* TreeUpIterator_Attach - attach tree branch to iterator and initialize
 * iterator */
void
TreeUpIterator_Attach(this, pFirst)
     PTreeUpIterator *this;
     PTreeNode      *pFirst;
{
	this->pCurr = pFirst;
}

/* TreeUpIterator_Next - return pointer to next item from tree branch */
int
TreeUpIterator_Next(this, ppItem)
     PTreeUpIterator *this;
     void          **ppItem;
{
	if (!this->pCurr)	/* end of iteration */
		return 0;

	*ppItem = this->pCurr->pItem;
	this->pCurr = this->pCurr->pParent;
	return 1;
}
